ftp.cs.arizona.edu/ftp.cs.arizona.edu.tar/ftp.cs.arizona.edu/icon/newsgrp/group99a.txt/000210_icon-group-sender _Thu Oct 7 12:26:03 1999.msg

Internet Message Format | 2000-09-20 | 10KB

Return-Path: <icon-group-sender>
Received: (from root@localhost)
    by baskerville.CS.Arizona.EDU (8.9.1a/8.9.1) id MAA28331
    for icon-group-addresses; Thu, 7 Oct 1999 12:25:00 -0700 (MST)
Message-Id: <[e-mail]>
Date: Thu, 07 Oct 1999 09:33:25 -0700
From: Steve Wampler <[e-mail]>
X-Accept-Language: en
To: [e-mail]
CC: Steve Wampler <[e-mail]>
Subject: Re: A small puzzle
Errors-To: [e-mail]
Status: RO

This is a multi-part message in MIME format.
--------------D3D91CF3B7EB1333F3CB751F
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit

Steve Wampler wrote:
>
>    Write an Icon program to generate the pairings in a round-robin
>    tournament.  The program should accept the player names as
>    command line arguments (see the example below).
>

Ok, I don't think anyone else is going to submit a response, so here's
a quick summary.  Two people submitted working solutions - Gregg Townsend
and Andru Luvisi.  Andru's solution needs a (very) minor modification
to meet the requirement of using names from the command-line arguments,
but that's a pretty trivial change (I've made it in the attachment).
Gregg's solution is pretty interesting, it's crafted from scratch and
uses a mapping to single characters to allow string scanning and cset
operations - it's also the best-commented.  The use of csets limits
the tournament to at most 255 players, which is probably ok in most
real-world situations.  Gregg's solution is also attached.

One person gave a nice graph-theory-based analysis of the problem
with an algorithm for the solution, but without actual code.  The
analysis is good, though the algorithm is mildly wasteful of space.
(I won't repost the algorithm here since it has already shown up in
this group, but you might take a look at it and see if you can
identify the wasted space...).

No one tried either of the two challenges: (a) add an option to
specify the number of 'real' courts and (b) arrange the ordering
so the last round pairs players in the same order they appear on
the command line.  It's probably just as well that no one did (a),
as Andru pointed out, the ugliness is when the number of courts
exceeds the number of players. I've included in my code a solution to
(b) - the same strategy could be applied to Andru's solution, but
would need a different initial pattern.

My code is similar to Andru's, using the same basic algorithm
(which is a varient of the graph-based algorithm already posted.
You might look to see how the use of the space is improved.
Can you figure out how to use still less space?)

After seeing how nicely Gregg's code was commented, I went back
and added some comments...

----------------------------------------------------------------
# Generate the pairings for each round of a round-robin tournament.
#
# Usage: roundrobin list-of-players...
#
procedure main(args)
    if *args = 0 then args := ["alice", "bonnie", "carole"]
    doRoundRobin(args)
end

# Do the scheduling for the tournament.
#
#   This implementation produces an 'interesting' final round.  If the
#   order of the names given on the command line corresponds to the
#   seeding order for the tournament, then the final round pairs
#   the top two seeds, the next two, and so on.  This should help
#   keep the spectators around, allowing you to make more money
#   on refreshments.  If you don't want this, comment out the line:
#
#     names := reorder(names)
#
procedure doRoundRobin(names)
    # force an even number of contestents
    if *names % 2 = 1 then put(names,"bye")

    names := reorder(names)

    every outPairs(1 to *names-1, names := adjust(names))
end

# Adjust the list of players for the next round.
#
#   The algorithm is "leave the first alone, rotate the rest one position"
#
procedure adjust(playerList)
    return playerList[1:2] ||| playerList[3:0] ||| playerList[2:3]
end

# Display the pairings for a single round.
#
procedure outPairs(i, names)
    write("Round ",i)
    every c := 1 to (*names/2) do {   # pair from edges toward center
        write("\tCourt ", right(c,2), ": ", names[c], " vs ", names[-c])
        }
end

# Reorder the names so the first call to adjust() produces an ordering
#   that ensures the final round pairs the players in the original order
#
procedure reorder(names)
    every new := put([], names[(1 to *names by 2) | (*names to 2 by -2)])
    return new
end
-------------------------------------------------------

I hope some of you had fun thinking about this problem!
--
Steve Wampler-  SOLIS Project, National Solar Observatory
[e-mail]
--------------D3D91CF3B7EB1333F3CB751F
Content-Type: text/plain; charset=us-ascii;
 name="andru.icn"
Content-Disposition: inline;
 filename="andru.icn"
Content-Transfer-Encoding: 7bit

procedure main(args)
 every gameset := turnament(args)
  do every write((left((pair := !gameset)[1], 5) || left(pair[2], 5)) | "");
end

procedure turnament(people)
 local i;
 local stationary_player, gameset;

 stationary_player := (*people % 2 = 0 & get(people)) | "Buy";
 every 1 to *people do {
   gameset := [ [ stationary_player, people[*people] ] ];
   every gameset |||:= [[people[ i := 1 to (*people - 1) / 2 ], people[-i-1]]];
   suspend gameset;
   push(people, pull(people));
 }
 fail;
end

--------------D3D91CF3B7EB1333F3CB751F
Content-Type: text/plain; charset=us-ascii;
 name="gregg.icn"
Content-Disposition: inline;
 filename="gregg.icn"
Content-Transfer-Encoding: 7bit

## rrobin.icn -- generate round-robin pairings
#
#  usage:  rrobin name...
#
#  1-Oct-1999 / gmt  (inspired by a Steve Wampler puzzle challenge)
#
#  This program generates an optimal set of pairings for a round-robin
#  tournament.  For an even number N of players, N-1 rounds on N/2
#  courts are needed.  For N odd, N rounds on N/2 courts are required,
#  with a "bye" on an additional "court" at each round.

procedure main(args)
   local n, ct, labels, round, name1, name2

   if *args > 255 then
      stop("too many names")
   labels := (&cset -- ' ')[1+:*args]
   n := 0
   every round := pairs(labels) do round ? {
      write("Round ", n +:= 1)
      ct := 0
      while =" " do {
         name1 := args[upto(move(1), labels)]
         name2 := args[upto(move(1), labels)]
         write("\tCourt  ", ct +:= 1, ": ", name1, " vs ", name2)
         }
      if name1 := args[upto(labels -- round, labels)] then
         write("\tCourt  ", ct +:= 1, ": bye vs ", name1)
      }
end


## pairs(players) -- generate pairings for round-robin tournament
#
#  The characters of the string "players" label contestants to be paired
#  in a round-robin tournament.  This procedure generates an optimal set
#  of rounds such that at the end each player is paired exactly once with
#  each other player.  Characters in "players" must be unique and must not
#  include the space character (' '); thus a maximum of 255 contestants
#  can be handled.
#
#  Output is a sequence of strings where each string represents one
#  round of disjoint pairings.  Each pairing consists of three
#  characters: a space followed by the labels of the two contestants.
#
#  1-Oct-1999 / gmt

procedure pairs(players)
   if *players < 2 then
      fail
   else if *players = 2 then
      return " " || players
   else if *players % 2 = 1 then
      suspend oddpairs(players)
   else
      suspend evenpairs(players)
end



## oddpairs(players) -- generate pairings for an odd number of contestants
#
#  With an odd number N of players, the optimum solution requires N rounds
#  on N/2 courts with one "bye" in each round.  A regular pattern produces
#  the pairings:  Each round pairs 1 vs N, 2 vs N-1, 3 vs N-2, etc.,
#  designating a different player as #1 for each of N rounds.

procedure oddpairs(players)
   local n, i, j, round

   n := *players
   every i := 1 to n do {
      round := ""
      every j := 1 to n / 2 do
         round ||:= " " || players[j] || players[n - j]
      players := players[2:0] || players[1]
      suspend round
      }
end



## evenpairs(players) -- generate pairings for an even number of contestants
#
#  With an even number N of players, N-1 rounds on N/2 courts are needed.
#  There are no byes.  First, the players are divided into two groups,
#  and the pairings within each group are enumerated in parallel.  If the
#  groups are odd-sized, there is a bye within each group at each round;
#  the two unoccupied players play each other across group boundaries.
#  After the intra-group competition, the remaining combinations of
#  cross-group pairings are enumerated.

procedure evenpairs(players)
   local half, odd, grp1, grp2, p1, p2, round, step, i

   half := *players / 2
   odd := half % 2
   grp1 := players[1+:half]
   grp2 := players[0-:half]

   every put(p1 := [], pairs(grp1))
   every put(p2 := [], pairs(grp2))
   while round := get(p1) || get(p2) do {
      if odd = 1 then
         round ||:= " " || (players -- round)
      suspend round
   }

   grp2 := grp2 || grp2
   every step := odd to half - 1 do {
      round := ""
      every i := 1 to half do
         round ||:= " " || grp1[i] || grp2[i + step]
      suspend round
      }
end


--------------D3D91CF3B7EB1333F3CB751F--